package com.sheng.project.test.sort;

/**
 * 快速排序：保证走完之后，比基准点小的值都位于基准点左边，比基准点大的值都位于基准点右边，然后分别对基准点左右部分再次进行快排迭代
 *
 * @author liusheng
 * @date 2022/08/19
 */
public class QuickSort {

    public static void quick(int[] ints, int left, int right) {
        if (left > right) {
            return;
        }
        // 设置基准点，一般选第一个元素即可
        int base = ints[left];
        // 定义左右指针
        int l = left;
        int r = right;
        // 左指针从左往右找即基准大的数，右指针从右往左找比基准小的，在左右边界大小符合时进行位置调换
        while (l < r) {
            // 从右边界开始找，找到第一个比基准小的
            while (base <= ints[r] && l < r) {
                r--;
            }
            // 从左边界开始找，找到第一个比基准大的
            while (base >= ints[l] && l < r) {
                l++;
            }
            // 将比基准小的数和比基准大的数位置进行调换，将比基准小的数放到基准的左边，比基准大的数放到基准的右边
            if (l < r) {
                int t = ints[r];
                ints[r] = ints[l];
                ints[l] = t;
            }
        }
        // 此时l == r，左右边界相遇，将基准点位置的值和左边界位置的值交换
        ints[left] = ints[l];
        ints[l] = base;

        quick(ints, left, r - 1);
        quick(ints, r + 1, right);
    }
}
